

#include "mythread.h"
#include <signal.h>
#include <setjmp.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>

#define READY_STATE 0
#define BLOCKED_STATE 1
#define TERMINATED_STATE 2

#define THREAD_UNINITIALIZED 0
#define THREAD_INITIALIZED 1

node_t *first = NULL; /* first node in the queue */
node_t *last = NULL;  /* last node in the queue */
int cnt = 0; /* count of number of nodes in the list, not really used */
int threadNum = 0;  /* Keeps track of the total number of threads */
int readyThreads = 0;  /* Keeps track of the total number of threads that are in ready state at any time, does not include idle thread */
int initFlag = 0;  /* Flag that indicates whether the library has been initialized or not */
int currentThreadNum = 0;  /* This is the number of the thread that is currently executing */

/* Encrypts a pointer so that it can be stored in a jmp_buf struct */
unsigned long int mangle64(unsigned long int);

/**
 * Add a new node to the linked list queue, at the end
 *
 * \param An input value to be added to the list
 * \return nothing
*/
void addLast ( node_t* );

/**
 * Remove a thread from the beginning of the list
 *
 * \return Nothing
 */
void removeFirst ();

/**
 * Move thread from the beginning of the queue to the end
 *
 * \param Thread to move to end of list
 * \return Nothing
 */
void moveFirst();

/**
 * Searches the queue to find out if the currently blocked thread at the front of the queue can be unblocked
 * This basically means that it searches the list for the thread and checks to see if its status is terminated
 *
 * \param The thread to check if it can be unblocked
*  \return  node_t* that indicates whether thread should still be blocked: full node means no longer blocked, NULL means still blocked
*/
node_t * isBlocked();

/**
 * Searches the queue to find out if the thread that the current thread is trying to join exists
 *
 * \param The thread ID to check if it exists
 * \param Pointer to first thread in list
*  \return  integer that represents whether or not the thread exists: 0 means the thread does not exist, 1 means the thread exists
*/
int threadExists( mythread_t );

/* Prototype for wrapper function that will be the central part of the library, also performs library initialization */
void wrapper(void);

/* Prototype for function that will be called when the idle thread is running */
void idle(void);

/**
 * mythread_self -  returns thread id of running thread
 *
 *  \return thread ID of the currently executing thread
 */
extern mythread_t mythread_self(void){
	return (first->threadId);
}

/**
 * mythread_create - prepares context of new_thread_ID as start_func(arg),
 * attr is ignored right now.
 *
 * \param id of the new thread
 * \param attribute that indicates a user-defined stack size
 * \param pointer to the function that should be called when thread is created
 * \param pointer to any argument to the function requires
 * \return integer that indicates successful return of mythread_create function, 0 indicates success
 */
extern int mythread_create(mythread_t *new_thread_ID, mythread_attr_t *attr,
				void * (*start_func)(void *),void *arg){
	/* This is the new node_t object that will be the TCB for the new thread we are creating */
	/* allocate memory for this node in the queue*/
    node_t *newThread;
	
	/* If the library has not been initialized yet, then we call the wrapper to set up the idle and main threads */
	if(initFlag == 0){
		/* Create a TCB for main thread */
		node_t *mainThread;
		mainThread = (node_t *) malloc ( sizeof(node_t) );
		if (mainThread == NULL) {
			printf("Unable to add new thread information; no more memory available\n");
			return 1;
		}
		
		/* Main thread is always thread 0 */
		mainThread->threadId = threadNum;
		threadNum++;
	
		mainThread->status = READY_STATE;
		mainThread->initFlag = THREAD_INITIALIZED;
		mainThread->blockedFor = -1;
		mainThread->returnedStatus = 0;
	
		/* Add main thread to the queue and increment number of ready threads, this is the first thread in a ready state to execute */
		addLast(mainThread);
		readyThreads++;
			
		/* Create a TCB for idle thread */
		node_t *idleThread;
		idleThread = (node_t *) malloc ( sizeof(node_t) );
		if (idleThread == NULL) {
			printf("Unable to add new thread information; no more memory available\n");
			return 1;
		}
		
		/* Idle thread is always thread 1 */
		idleThread->threadId = threadNum;
		threadNum++;
			
		idleThread->status = READY_STATE;
		idleThread->initFlag = THREAD_INITIALIZED;
		idleThread->blockedFor = -1;
		idleThread->returnedStatus = 0;
			
		/* Create an execution context with a pointer to the idle function */
		jmp_buf context;
		/* Install the idle pointer here */
		unsigned long int idleAddress = (unsigned long int) &idle;
		context->__jmpbuf[7] = (unsigned long int) mangle64(idleAddress);
			
		/* Allocate a default stack for the idle thread */
		unsigned int *newStack;
		newStack = (unsigned int *) malloc(SIGSTKSZ);
		newStack = newStack + SIGSTKSZ - 1;
			
		context->__jmpbuf[6] = mangle64((unsigned long int) newStack);
		memcpy(idleThread->currentContext, context, sizeof(jmp_buf));
	
		/* Add idle thread to the queue but do not increment number of ready threads because that variable is used to represent 
		threads other than the idle thread, that deserve priority effectively, our way of making the idle thread have less priority */
		addLast(idleThread);
			
		initFlag = 1;
	}

	newThread = (node_t *) malloc ( sizeof(node_t) );
    if (newThread == NULL) {
        printf("Unable to add new thread information; no more memory available\n");
        return 1;
    }
	
	/* The rest of the create function initializes the node_t TCB structure for the new thread */
	newThread->threadId = threadNum;
	*new_thread_ID = threadNum;
	threadNum++;
	
	newThread->status = READY_STATE;
	newThread->initFlag = THREAD_UNINITIALIZED;
	newThread->blockedFor = -1;
	newThread->returnedStatus = 0;
	
	/* The next four instructions are part of preparing the jmp_buf structure's PC */
	jmp_buf context;
	/*Install the wrapper here*/
	unsigned long int wrapperAddress = (unsigned long int) &wrapper;
	context->__jmpbuf[7] = (unsigned long int) mangle64(wrapperAddress);
	newThread->funcAddress = start_func;
	newThread->funcArg = arg;
	
	/* The next block allocates the stack for this thread and saves the new SP in the jmp_buf */
	/***************** NEED TO ALIGN THE STACK AND RAISE IT FROM THE BOTTOM ************************/
	unsigned int *newStack;
	mythread_attr_t stackSize;
	if(attr != NULL){
		stackSize = *attr;
	}
	/* If there is no attr, then use the default stack size */
	if(attr == NULL){
		newStack = (unsigned int *) malloc(SIGSTKSZ);
		newStack = newStack + SIGSTKSZ - 1;
	}else{
		/* Make sure that the user's provided stack size is not less than the minimum possible, if it is below set it to default */
		if(stackSize < sizeof(sigset_t)){
			newStack = (unsigned int *) malloc(sizeof(sigset_t));
			newStack = newStack + sizeof(sigset_t) - 1;
		}else{
			newStack = (unsigned int *) malloc(stackSize);
			newStack = newStack + stackSize - 1;
		}
	}
	
	/* Align stack and place safety frame at bottom */
	/*printf("The stack is located at %x\n", newStack);
	printf("The size of a TCB is %x\n", sizeof(node_t));
	newStack = newStack - 64;
	printf("The stack is located at %x\n", newStack);*/
	
	context->__jmpbuf[6] = mangle64((unsigned long int) newStack);
	memcpy(newThread->currentContext, context, sizeof(jmp_buf));
	
	/* Add the new thread to the end of the queue */
	addLast(newThread);
	
	/* Increment the number of threads that are ready to execute */
	readyThreads++;
	
	return 0;
}

/**
 * mythread_yield - switch from running thread to the next ready one
 *
 * \return integer that indicates if the yield succeeded
 */
extern int mythread_yield(void){
	/* The setjmp call here will save the current execution context and store it in TCB to be restored once thread returns to front of queue */
	jmp_buf currentState;
	if(setjmp(currentState) != 0){
		/* Return control to calling thread  */
		return 0;
	}
	memcpy(first->currentContext, currentState, sizeof(jmp_buf));
	/* Move the yielding thread to the end of the queue */
	moveFirst();
	
	/* Handle the current thread if its status is terminated */
	while((first->status) == TERMINATED_STATE){
		/* If this node has made it back to the beginning of the queue, then all threads that needed its return information have exited
		Thus, it is now ok to remove the terminated thread from the queue
		*/
		removeFirst();
	} 
	
	/* Longjmp to dispatch the next thread */
	longjmp(first->currentContext,1);
	
	return 0;	
}

/**
 * mythread_join - suspend calling thread if target_thread has not finished,
 * enqueue on the join Q of the target thread, then dispatch ready thread;
 * once target_thread finishes, it activates the calling thread / marks it
 * as ready.
 *
 * \param id of the target thread to wait on
 * \param return status of the target thread
 * \return integer flag that indicates if the join succeeded: 0 for success, 1 for failure
 */
extern int mythread_join(mythread_t target_thread, void **status){
	/* Make sure target thread is valid */
	if((threadExists(target_thread)) != 1){
		return 0;
	}
	/* Set current thread to blocked */
	first->status = BLOCKED_STATE;
	readyThreads--;
	/* Set field indicating which thread the current thread will be waiting on */
	first->blockedFor = target_thread;
	
	node_t *blockedFlag = isBlocked(first);
	
	/* No longer blocked */
	while(1){
		if(blockedFlag != NULL){
			/* Set the return status of the current thread to that of the thread that it blocked for, used to pass status back to calling thread */
			*status = &blockedFlag->returnedStatus;
			/* Return control back to the thread that was blocked on a join call */
			break;
		} else{
			mythread_yield();
			blockedFlag = isBlocked(first);
		}
	}
		
	/* Once unblocked we set the thread back to ready here and set the return status  of the target thread*/
	first->status = READY_STATE;
	first->blockedFor = -1;
	
	/* Return control to calling thread  */
	return 0;
}

/**
 * mythread_exit - exit thread, awakes joiners on return
 * from thread_func and dequeue itself from run Q before dispatching run->next
 *
 * \param return value, indicates success (0) or failure (1)
 */
extern void mythread_exit(void *retval){
	/* Set the status of the exiting thread to terminated (2) */
	first->status = TERMINATED_STATE;
	readyThreads--;
	
	/* Set the return value of the terminating thread to the parameter passed in */
	int *returnValue = (int *) retval;
	if(retval != NULL)
	{
		first->returnedStatus = *returnValue;
	}else{
		first->returnedStatus = 0;
	}
	
	/* Move the newly terminated thread to the end of the queue */
	moveFirst();
	
	/* Handle the current thread if its status is terminated */
	while((first->status) == TERMINATED_STATE){
		/* If this node has made it back to the beginning of the queue, then all threads that needed its return information have exited
		Thus, it is now ok to remove the terminated thread from the queue
		*/
		removeFirst();
	}
	
	/* Longjmp to dispatch the next thread */
	longjmp(first->currentContext,1);
}

/**
 * Wrapper function that forms the main dispatching system for the thread library.  Also initializes the main and idle threads.
 *
 */
void wrapper(void){
	/* When a thread is new and it is being dispatched with potential arguments, we need to call the function with arguments */
	/************** FIGURE OUT HOW TO PASS THE ARGUMENTS AND CALL THE FUNCTION ****************/
	void *(*start_func)(void *);
    start_func = (first->funcAddress);
	start_func(first->funcArg);
	
	/************** EXIT THE THREAD WHEN IT RETURNS **************/
	
}

/**
 * Function that will be called when the idle thread is running, will loop until there is a thread ready to be switched to
 *
 */
void idle(void){
	while(1){
		/* Wait until a thread is ready to execute and then return control to wrapper for dispatching */
		if(readyThreads > 0){
			/*printf("I am the idle thread and I have been dispatched!!!!\n\n");*/
			mythread_yield();
		}else{
			exit(0);
		}
	}
}

unsigned long int mangle64(unsigned long int addr)
{
    unsigned long int ret;
    asm volatile("xorq %%fs:0x30,%0\n"

        "rolq $0x11,%0\n"
        : "=r" (ret)
        : "0" (addr));

    return ret;
}

/**
 * Add a new node to the linked list queue, at the end
 *
 * \param An input value to be added to the list
 * \return nothing
*/
void addLast ( node_t *newThread ) {
	/* connect the new thread at the end of the existing list */
    newThread->next = NULL;
    newThread->prev = last;

    /* don't forget to update the head and tail of the list */
    if (last != NULL)
        last->next = newThread;
    if (first == NULL)
        first = newThread;
    last = newThread;

    cnt++;

    return;
}

/**
 * Remove a thread from the beginning of the list
 *
 * \return Nothing
 */
void removeFirst () {
    node_t *n;
    node_t *p;

    p = NULL;
    n = first;
    first = (*n).next;
	if(first != NULL){
		(*first).prev = NULL;
	}

    free (n);  /* no memory leaks! */
	
	cnt--;

    return;
}

/**
 * Move thread from the beginning of the queue to the end
 *
 * \return Nothing
 */
void moveFirst(){
	node_t *thread = first;
	
	if((first->next) == NULL){
		return;
	}
	
	(first->next)->prev = NULL;
	first = first->next;
	
	last->next = thread;
	thread->prev = last;
	thread->next = NULL;
	last = thread;
	
	return;
}

/**
 * Searches the queue to find out if the currently blocked thread at the front of the queue can be unblocked
 * This basically means that it searches the list for the thread and checks to see if its status is terminated
 *
 *  \return  node_t* that indicates whether thread should still be blocked: full node means no longer blocked, NULL means still blocked
 */
node_t * isBlocked(){
	
	node_t *thread = first;
	
	/* Get ID of thread that we want to check its status for termination */
	mythread_t waitingForId = thread->blockedFor;
	node_t *current = first;
	
	/* Increment list checking for the thread that the current thread was blocked for, then check its status to see if it has terminated */
	while(current != NULL){
		if((current->threadId) == waitingForId){
			if((current->status) == 2){
				return current;
			} else{
				return NULL;
			}
		}
		current = current->next;
	}
	
	return 0;
}

/**
 * Searches the queue to find out if the thread that the current thread is trying to join exists
 *
 *  \return  integer that represents whether or not the thread exists: 0 means the thread does not exist, 1 means the thread exists
 */
int threadExists( mythread_t target ){
	mythread_t targetId = target;
	node_t *current = first;
	
	/* Increment list checking for the thread that we want to know if it exists */
	while(current != NULL){
		if((current->threadId) == targetId){
			if((current->status) == 2){
				return 0;
			} else{
				return 1;
			}
		}
		current = current->next;
	}
	
	return 0;
}

/**
 * Prints the contents of the queue (each thread's ID), used for queue testing purposes
 *
 */
extern void printQueue(){
	node_t *current = first;
	
	printf("Number of threads is: %d\n", cnt);
	
	/* Increment list printing each thread ID */
	while(current != NULL){
		printf("Current thread: %d\n", current->threadId);
		current = current->next;
	}
}

/**
 * Main function used for testing purposes
 *
 * \param none
 * \return 0 on successful completion; there are no fatal errors
 */
/*
int main ( void ) {
	int i = 0;
	node_t *newThread;
	for(i = 0;i < 5;i++){
		newThread = (node_t *) malloc ( sizeof(node_t) );
		if (newThread == NULL) {
			printf("Unable to add new thread information; no more memory available\n");
			return 1;
		}
		newThread->threadId = i;
		if(newThread == NULL){
			printf("New thread pointer is null before\n");
		}
		addLast(newThread);
	}
	
	printQueue();
	
	removeFirst();
	
	printQueue();
	
	removeFirst();
	
	printQueue();
	
	moveFirst();
	
	printQueue();
	
	int flag = threadExists(0);
	if(flag == 1)  printf("Thread 0 exists!\n");
	else printf("Thread 0 does not exist!\n");
	
	flag = threadExists(2);
	if(flag == 1)  printf("Thread 2 exists!\n");
	else printf("Thread 2 does not exist!\n");
	
	printQueue();
	
    return 0;

}
*/
